#include <iostream>
#include <fstream>
#include <cstring>

#include "lex.hpp"

using namespace std;

static bool is_digit(char c) {
	return c >= '0' && c <= '9';
}

static bool is_letter(char c) {
	return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
}

static bool is_space(char c) {
	return c == ' ' || c == '\t' || c == '\r' || c == '\n';
}

static CharType classify_char(char c) {
	switch(c) {
		case '+': return CharType::ADD;
		case '-': return CharType::SUB;
		case '*': return CharType::MUL;
		case '/': return CharType::DIV;
		case '%': return CharType::MOD;
		case '=': return CharType::EQ;
		case '>': return CharType::GT;
		case '<': return CharType::LT;
		case '!': return CharType::NOT;
		case '&': return CharType::AND;
		case '|': return CharType::OR;
		case '(': return CharType::LBRAC;
		case ')': return CharType::RBRAC;
		case '{': return CharType::LCBRAC;
		case '}': return CharType::RCBRAC;
		case ',': return CharType::COMMA;
		case ';': return CharType::SEMI;
		case '_': return CharType::UNDERLINE;
		default: {
			if (is_digit(c)) {
				return CharType::DIGIT;
 			} else if (is_letter(c)) {
				return CharType::LETTER;
 			} else if (is_space(c)) {
				return CharType::EPSILON;
 			} else {
 				cerr << "Illegal character: \'" << c << "\'"<< endl;
 				exit(-1);
 			}
		}
	}
}

void print_states(int state_num, int char_num, map<int, int> &state_types);

// 打印自动机的规则
static void print_dfa(
		int state_num, int char_num, 
		map<int, int> &state_types,
		vector<map<int, int>> &rules
	) {
	print_states(state_num, char_num, state_types);

	for (int i = 0; i < state_num; ++i) {
		cout << "State" << i << "\t";
		for (int j = 0; j < char_num; ++j) {
			auto res = rules[i].find(j);
			if (res == rules[i].end()) {
				cout << "{}";
			}else {
				cout << (*res).second;
			}
			cout << "\t";
		}
		cout << endl;
	}
}

// 将状态加入到状态集合
// 若状态已加入，则返回序号
// 若状态未加入，则将其加入，并返回其序号
static int insert_set(vector<unordered_set<int>> &sets, unordered_set<int> set0) {
	int cnt;
	for (cnt = 0; cnt < sets.size(); ++cnt) {
		if (sets[cnt] == set0) {
			return cnt;
		}
	}
	sets.push_back(set0);
	return cnt;
}

// 将set1复制到set0
static void copy_set(unordered_set<int> &set0, const unordered_set<int> &set1) {
	set0.clear();
	for (auto iter = set1.begin(); iter != set1.end(); ++iter) {
		set0.insert(*iter);
	}
}

static void get_state_type(NFA &nfa, const unordered_set<int> &set, int &type, int &val) {
	for (auto iter = set.begin(); iter != set.end(); ++iter) {
		int st = nfa.get_state_type(*iter);
		if (st == StateType::EXIT || st == StateType::START) {
			type = st;
			if (st == StateType::EXIT) {
				val = nfa.get_state_val(*iter);
			}
			return;
		}
	}
	type = StateType::INTER;
}

static void print_set(const unordered_set<int> &set) {
	for (auto iter = set.begin(); iter != set.end(); ++iter) {
		cout << *iter << " ";
	}
	cout << endl;
}

// DFA构造函数
// 从NFA构建DFA
DFA::DFA(NFA &nfa) {
	cout << "Building DFA from NFA..." << endl;
	state_num = 0;
	char_num = nfa.char_num;

	vector<unordered_set<int>> sets;
	unordered_set<int> src, dst0, dst1;

	// 插入初始闭包
	src.insert(0);
	nfa.closure(src, dst0);
	insert_set(sets, dst0);

	int cnt = 0;
	do {
		copy_set(src, sets[cnt]);
		rules.push_back(map<int, int>());
		int type, val;
		get_state_type(nfa, src, type, val);
		state_types[cnt] = type;
		if (type == EXIT) {
			state_vals[cnt] = val;
		}

		for (int i = 0; i < char_num; ++i) {
			nfa.go(src, CharType(i), dst0);
			nfa.closure(dst0, dst1);
			if (dst1.empty()) { // 转移状态为空直接跳过
				continue;
			}
 			int ind = insert_set(sets, dst1);
			rules[cnt][i] = ind;
		}
		++cnt;
	} while(cnt < sets.size());
	state_num = sets.size();
	/*for (int cnt = 0; cnt < sets.size(); ++cnt) {
		cout << cnt << ": "; 
		print_set(sets[cnt]);
	}*/
	cout << "Finished" << endl << endl;
}

void DFA::print_rules() {
	print_dfa(state_num, char_num, state_types, rules);
}

// 判断两状态是否为同一类型
bool DFA::is_same_type(int state0, int state1) {
	int type0, type1;
	type0 = state_types[state0];
	type1 = state_types[state1];

	switch (type0) {
		case StateType::START:
		case StateType::INTER: return type1 != StateType::EXIT;
		// EXIT状态须满足返回token类型相同
		case StateType::EXIT: return (type0 == type1) && (state_vals[state0] == state_vals[state1]);
		default: return false;
	}
}

// 初次划分，将相同类型的状态划分为同一集合
void DFA::first_split(vector<vector<int>> &sets) {
	for (int i = 0; i < state_num; ++i) {
		int j;
		for (j = 0; j < sets.size(); ++j) {
			if (this->is_same_type(i, sets[j][0])) {
				sets[j].push_back(i);
				break;
			}
		}
		if (j == sets.size()) {
			sets.push_back(vector<int>());
			sets.back().push_back(i);
		}
	}
}

bool DFA::is_inside(int state, vector<int> &state_set) {
	if (state == -1) { // -1 表示无可转移状态
		return true; // 无可转移状态也视为在原集合中
	}
	for (int cnt = 0; cnt < state_set.size(); ++cnt) {
		if (state == state_set[cnt]) {
			return true;
		}
	}
	return false;
}

void DFA::split_set(vector<int> &set, int char_type, vector<vector<int>> &result) {
	result.clear();
	if (set.size() == 1) { // 大小为1则必不能再拆分，直接返回
		result.push_back(vector<int>());
		result.back().push_back(set[0]);
		return;
	}

	map<int, bool> dst_types;
	for (int cnt = 0; cnt < set.size(); ++cnt) {
		int dst;
		auto res = rules[set[cnt]].find(char_type);

		if (res != rules[set[cnt]].end()) { // 记录可转移状态
			dst = (*res).second;
		} else { // 无可转移状态使用-1标记
			dst = -1;
		}

		dst_types[set[cnt]] = is_inside(dst, set);	// 检查转移状态是否在原集合中，存入表中
	}

	for (int i = 0; i < set.size(); ++i) {
		int j;
		for (j = 0; j < result.size(); ++j) {
			if (dst_types[set[i]] == dst_types[result[j][0]]) { // 状可转移状态类型相同
				result[j].push_back(set[i]);
				break;
			}
		}
		if (j == result.size()) {
			result.push_back(vector<int>());
			result.back().push_back(set[i]);
		}
	}
}

// 根据生成的状态集合将rules, state_types, state_vals重新映射
void DFA::remapping(vector<vector<int>> &sets, vector<map<int, int>> &new_rules, map<int, int> &new_state_types, map<int, int> &new_state_vals) {
	map<int, int> old_2_new; // 将旧的状态映射到新的状态集合
	for (int i = 0; i < sets.size(); ++i) {
		new_rules.push_back(map<int, int>());
		for (int j = 0; j < sets[i].size(); ++j) {
			old_2_new[sets[i][j]] = i;
		}
	}
	/*for (auto iter=old_2_new.begin(); iter != old_2_new.end(); ++iter) {
		cout << "old: " << (*iter).first << ", new: " << (*iter).second << endl;
	}
	cout << endl;*/

	for (int i = 0; i < sets.size(); ++i) {
		for (int j = 0; j < char_num; ++j) {
			auto res = rules[sets[i][0]].find(j); // 同一状态集合的状态不可分，以第0状态代表其他状态
			if (res != rules[sets[i][0]].end()) {
				new_rules[i][j] = old_2_new[(*res).second];
			}
		}
	}

	for (int i = 0; i < sets.size(); ++i) {
		int state_type = state_types[sets[i][0]];
		new_state_types[i] = state_type;
		if (state_type == StateType::EXIT) {
			new_state_vals[i] = state_vals[sets[i][0]];
		}
	}
}

// 最小化
void DFA::minimise() {
	cout << "Minimising..." << endl;
	vector<vector<int>> sets, result, tmp;
	this->first_split(sets);

	for (int i = 0; i < char_num; ++i) {
		result.clear();
		for (int j = 0; j < sets.size(); ++j) {
			split_set(sets[j], i, tmp);
			result.insert(result.end(), tmp.begin(), tmp.end());
		}
		sets = result;
	}

	vector<map<int, int>> new_rules;
	map<int, int> new_state_types, new_state_vals;
	cout << "remapping" << endl;
	this->remapping(sets, new_rules, new_state_types, new_state_vals);
	
	state_num = sets.size();
	rules = new_rules;
	state_types = new_state_types;
	state_vals = new_state_vals;
	cout << "Finished" << endl << endl;
}

// 打开C--文件
void DFA::openfile(char *input_file) {
	if (input_file != nullptr) {
		infile = fopen(input_file, "r");
		cout << "Opened file " << input_file << endl << endl;
	}
}

// 关闭C--文件
void DFA::closefile() {
	if (infile != nullptr) {
		fclose(infile);
		cout << "Closed file"<< endl << endl;
	}
}

// 从buffer中弹出指定长度字符串，返回字符指针
char *DFA::dump(int len) {
	char *str = new char[len+1];
	for (int cnt = 0; cnt < len; ++cnt) {
		str[cnt] = buffer.front();
		buffer.pop_front();
	}
	str[len] = 0;
	return str;
}

// 从buffer中弹出指定长度字符串，不返回值
void DFA::pop(int len) {
	for (int cnt = 0; cnt < len; ++cnt) {
		buffer.pop_front();
	}
}

int DFA::get_token(Token &tk) {
	if (infile == nullptr) {
		cout << "Please input C file before getting token." << endl;
		return -1;
	}

	char c;
	int state = 0;

	if (buffer.empty()) {
		c = fgetc(infile);
		if (c != EOF) {
			buffer.push_back(c);
		} else {
			return -1;
		}
	}

	while (1) {
		int this_char = int(classify_char(buffer.back()));
		auto res = rules[state].find(this_char);

		if (res == rules[state].end()) {
			if (state_types[state] == StateType::EXIT) { // 符合退出条件
				tk.ty = state_vals[state];
				tk.val = this->dump(buffer.size()-1);
				return 0;
			} else { // 未达到退出状态就没有可到达状态，异常
				cerr << "It should be exit state when there is no reachable state. ";
				cerr << "state = " << state << " this_char = " << '\'' << buffer.back() << '\'' << endl;
				exit(-1);
			}
 		} else { // 中间状态
 			if (state == 0 && classify_char(buffer.back()) == CharType::EPSILON) {
 				buffer.pop_back();
 			}
 			state = (*res).second;
 			c = fgetc(infile);
 			if (c != EOF) {
 				buffer.push_back(c); // 取出下一个字符
 			} else {
 				if (state_types[state] == StateType::EXIT) {
					tk.ty = state_vals[state];
					tk.val = this->dump(buffer.size());
					return -1;
 				} else {
 					return -1;
 				}
 			}
 		}
	}
}
